/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algoritmosGeneticos;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;


/**
 *
 * @author jorgeorm
 */
class CromosomaQueens {
    private int edad,nQueens; //Edad del cromosoma, cantidad de reinas
    private double aptitud; //Valor de la aptitud del cromosoma
    private int [] tablero; //Core del cromosoma con el tablero.
    private boolean [] libre; //Arreglo auxiliar para la función de aptitud, indica si una reina
                              //está libre de ataque.
    
    /*
     * @param n_reinas la cantidad de reinas del problema
     */
    public CromosomaQueens(int n_reinas)
    {
        this.nQueens=n_reinas;
        edad=0;
        aptitud= Double.NaN;
        tablero = new int [n_reinas];
        libre= new boolean [n_reinas];
        for(int i=0;i<nQueens;i++)libre[i]=true;
    }
    /*
     * @param n_reinas la cantidad de reinas del problema
     * @param config array con la configuración del cromosoma
     */
    public CromosomaQueens(int n_reinas, int [] config)
    {
        this.nQueens=n_reinas;
        edad=0;
        aptitud= Double.NaN;
        tablero = new int [n_reinas];
        libre= new boolean [n_reinas];
        for(int i=0;i<nQueens;i++){
            tablero[i]= config[i];
            libre[i]=true;
        }
    }
    
    public void calcularAptitud()
    {
        aptitud=((double)evaluarCromosoma())/((double)nQueens);
//        if(aptitud==1.0) {
//            System.out.println("Encontré Solución==========>>>>: "+this);
//        } 
//        else if(aptitud>0.9) System.out.println("Encontré Posible solución!!!!: "+this);        
    }
    
    //Calcula la cantidad de reinas libres
    //
    private int evaluarCromosoma()
    {
        int reinasBienPuestas=0;
        //Verifico por cada una de las reinas en el tablero si hay ataques en
        //Diagonales
        //
        for(int i=0; i<nQueens; i++)
        {
            if(libre[i]){
                contarDiagSupIzqInfDer(i, tablero[i]);
                contaraDiagSupDerInfIzq(i, tablero[i]);
                if(libre[i]) reinasBienPuestas++;
            } else continue;
        }
        return reinasBienPuestas;
    }
    
    private void contarDiagSupIzqInfDer(int cordX, int cordY)
    {
        //Verifico si ya registrè un ataque
        //
//        if(libre[cordX]){
            //verifica esta diagonal desde esa posición hacia DiagSupIzq
            //
            int posX, posY;
            for (int avanc=1;cordX-avanc>-1 && cordY-avanc>-1; avanc++){
                posX=cordX-avanc;
                posY=cordY-avanc;
                if(tablero[posX]==posY){
                    libre[posX]=false;
                    libre[cordX]=false;
                }
            }
            //verifica esta diagonal desde esa posición hacia DiagInfDer
            //
            for (int avanc=1;cordX+avanc<nQueens && cordY+avanc<nQueens; avanc++){
                posX=cordX+avanc;
                posY=cordY+avanc;
                if(tablero[posX]==posY){
                    libre[posX]=false;//Marco a reina encontrada con ataque
                    libre[cordX]=false;//Marco a la reina en la posicion CordX, 
                                       //con ataque
                }
            }
//        }
        
    }
    
    private void contaraDiagSupDerInfIzq(int cordX, int cordY)
    {
        //Verifico si ya registrè un ataque
        //
//        if(libre[cordX]){
            //verifica esta diagonal desde esa posición hacia DiagSupIzq
            //
            int posX, posY;
            for (int avanc=1;cordX-avanc>-1 && cordY+avanc>-1; avanc++){
                posX=cordX-avanc;
                posY=cordY+avanc;
                if(tablero[posX]==posY){
                    libre[posX]=false;//Marco a reina encontrada con ataque
                    libre[cordX]=false;//Marco a la reina en la posicion CordX, 
                                       //con ataque
                }
            }
            //verifica esta diagonal desde esa posición hacia DiagInfDer
            //
            for (int avanc=1;cordX+avanc<nQueens && cordY+avanc<nQueens; avanc++){
                posX=cordX+avanc;
                posY=cordY-avanc;
                if(tablero[posX]==posY){
                    libre[posX]=false;
                    libre[cordX]=false;
                }
//            }
        }
    }
    
    /*
     * Incrementa la edad del cromosoma
     * @param incremento el valor a incrementar
     */
    public void incrementarEdad(int incremento){
        edad+=incremento;
    }
    
    /*
     * No tiene valor de incremento, asume 1 por defecto
     */
    public void incrementarEdad()
    {
        incrementarEdad(1);
    }
    
    /*
     * Operador de reproducción
     * @param cromosomaPadre Cromosoma que va a dar parte de su material genetico.
     */
    public ArrayList<CromosomaQueens> reproducirCon(CromosomaQueens cromosomaPadre, int codonI, int posFin){
        
        
        CromosomaQueens hijo1, hijo2;
        
        //Debug
//        System.out.println(", PuntoFin: "+posFin);
        //reproducción cruce por orden "emparejamiento ordenado"
        int [] arrayHijo1, arrayHijo2;
        arrayHijo1= new int [nQueens];
        arrayHijo2= new int [nQueens];
        for(int i=0;i < nQueens; i++) //Pongo bandera para las incognitas
        {
            arrayHijo1[i]=-1;
            arrayHijo2[i]=-1;
        }
        //Copio los segmentos de cromosoma de los padres, el hijo1 sale del papa y el hijo2 de la mama, luego
        //el hijo1 deberá complementarse con los alelos de la madre, el hijo2 co los del padre.
        for(int i=codonI; i<=posFin;i++)
        {
            arrayHijo1[i]=cromosomaPadre.getTablero()[i];
            arrayHijo2[i]=this.tablero[i];
        }
        
        //Debug
        //
//        System.out.print("Hijo1 con incognitas: [");
//        for(int i=0;i<nQueens;i++)
//        {
//            System.out.print(arrayHijo1[i]+", ");
//        }
//        System.out.println("]");
//        System.out.print("Hijo2 con incognitas: [");
//        for(int i=0;i<nQueens;i++)
//        {
//            System.out.print(arrayHijo2[i]+", ");
//        }
//        
//        System.out.println("]");
        
        //Lleno las incognitas del tablero utilizando alelos de los padres de posFin a fin
        //
        int idxHijo1=0;
        int idxHijo2=0;
        for(int i=posFin+1; i<nQueens;i++)
        {
            //Me ubico en la primera variable de arrayHijo1
            while(arrayHijo1[idxHijo1]!=-1){
                if(idxHijo1<nQueens-1)idxHijo1++;
                if(idxHijo1==nQueens-1)break;
            }
            //Me ubico en la primera variable de arrayHijo2
            while(arrayHijo2[idxHijo2]!=-1){
                if(idxHijo2<nQueens-1)idxHijo2++;
                if(idxHijo2==nQueens-1)break;
            }
            
            if(!estaEnArray(arrayHijo1,tablero[i])){
                arrayHijo1[idxHijo1]=tablero[i];
                //Debug
//                System.out.println("Puse de Madre: "+tablero[i]);

            }
            if(!estaEnArray(arrayHijo2,cromosomaPadre.getTablero()[i])){
                arrayHijo2[idxHijo2]=cromosomaPadre.getTablero()[i];
                //Debug
//                System.out.println("Puse de Padre: "+cromosomaPadre.getTablero()[i]);
            }
//            System.out.println("Salio de verificar si está en array");
        }
        
        //Lleno las incognitas del tablero utilizando alelos de los padres de inicio a posFin
        //
        for(int i=0; i<=posFin;i++)
        {
            //Me ubico en la primera variable de arrayHijo1
            while(arrayHijo1[idxHijo1]!=-1){
                if(idxHijo1<nQueens-1)idxHijo1++;
                if(idxHijo1==nQueens-1)break;
            }
            //Me ubico en la primera variable de arrayHijo2
            while(arrayHijo2[idxHijo2]!=-1){
                if(idxHijo2<nQueens-1)idxHijo2++;
                if(idxHijo2==nQueens-1)break;
            }
            if(!estaEnArray(arrayHijo1,tablero[i])){
                arrayHijo1[idxHijo1]=tablero[i];
//                System.out.println("Puse de Madre: "+tablero[i]);

            }
            if(!estaEnArray(arrayHijo2,cromosomaPadre.getTablero()[i])){
                arrayHijo2[idxHijo2]=cromosomaPadre.getTablero()[i];
//                System.out.println("Puse de Padre: "+cromosomaPadre.getTablero()[i]);
            }
        }
        
        hijo1= new CromosomaQueens(nQueens, arrayHijo1);
        hijo2= new CromosomaQueens(nQueens, arrayHijo2);
        
        hijo1.calcularAptitud();
        hijo2.calcularAptitud();
        
        //ArrayList para dar los hijos
        ArrayList<CromosomaQueens> hijos=new ArrayList<CromosomaQueens>(2);
        hijos.add(hijo1);
        hijos.add(hijo2);
        return hijos;
    }
    
    /*
     * Operador de mutacion
     * @param cromoHijo Cromosoma resultante de la mutación del cromosoma madre. 
     * @Objetivo Mutar genera un numero al azar posRand, donde se introducirá la mutación en el cromosoma hijo. 
     *           Guarda el valor en el cromosoma padre antes de realizar la mutaciion, para ubicar en qué posicion
     *             se debe hacer la permutación .
     */
    public CromosomaQueens mutar(int posRand1, int posRand2)
    {
        CromosomaQueens cromoHijo;
        int posValue1, posValue2;
        
        int []tabTemp= Arrays.copyOf(tablero, nQueens);
        
        posValue1=tablero[posRand1];
        posValue2=tablero[posRand2];        
        
        tabTemp[posRand1]=posValue2;
        tabTemp[posRand2]=posValue1;
        
        cromoHijo=new CromosomaQueens(nQueens, tabTemp);
        cromoHijo.calcularAptitud();
        return cromoHijo;
    }
    
    private boolean estaEnArray(int[] array, int i) {
        // Busqueda binaria
        int tam=nQueens;
        int inicio, fin;
        inicio=0;
        fin=nQueens-1;
        int [] arrayTmp= Arrays.copyOf(array, nQueens);
        Arrays.sort(arrayTmp);
        
        boolean encontrado=false;
        int mitad=0;
        
        
        while(!encontrado && tam>1)
        {
            mitad=(int)Math.round(((double)inicio+fin)/2.0);
            if(i==arrayTmp[mitad]){
                encontrado= true;
                continue;
            }
            else{
                if(i<arrayTmp[mitad]){
                    fin=mitad;
                    
                }else if(i>arrayTmp[mitad]){
                    inicio=mitad;
                }
                tam=fin-inicio;
                        
            }
        }
        if(tam==1)encontrado=(i==arrayTmp[inicio])||(i==arrayTmp[fin]);
//DEBUG
//
//        System.out.print("=======Busqueda Binaria=======, Valor: "+i+", Result: "+encontrado+", Arreglo: [");
//        for(int j=0; j<nQueens; j++)
//        {
//            System.out.print(arrayTmp[j]+", ");
//        }
//        System.out.println("]");
//        System.out.println("Salio blucle estaEnArray");
        
        return encontrado;    
    }

    /*
     * Setters and Getters
     */
    public double getAptitud() {
        return aptitud;
    }

    public void setAptitud(double aptitud) {
        this.aptitud = aptitud;
    }

    public int getEdad() {
        return edad;
    }

    public void setEdad(int edad) {
        this.edad = edad;
    }

    public boolean[] getLibre() {
        return libre;
    }

    public void setLibre(boolean[] libre) {
        this.libre = libre;
    }

    public int getnQueens() {
        return nQueens;
    }

    public void setnQueens(int nQueens) {
        this.nQueens = nQueens;
    }

    public int[] getTablero() {
        return tablero;
    }

    public void setTablero(int[] tablero) {
        this.tablero = tablero;
    }
    
    @Override
    public Object clone(){
        CromosomaQueens cromo=new CromosomaQueens(nQueens, Arrays.copyOf(tablero, nQueens));
        cromo.setAptitud(aptitud);
        cromo.setEdad(edad);
        cromo.setLibre(Arrays.copyOf(libre,nQueens));
        return cromo;
    }

    @Override
    public String toString() {
        StringBuffer s_buff= new StringBuffer((2*nQueens)+1);
        s_buff.append("{");
        for(int i=0; i<nQueens; i++){
            s_buff.append(tablero[i]);
            if(i<nQueens-1)s_buff.append(',');
        }
        s_buff.append("}");
        return s_buff.toString();
    }

    @Override
    public boolean equals(Object obj) {
        CromosomaQueens objCromo;
        if(obj.getClass()!= this.getClass()) return false;
        else{
            objCromo=(CromosomaQueens)obj;
            if(this.nQueens!=objCromo.getnQueens()) return false;
            else if(this.aptitud!=objCromo.getAptitud()) return false;
            else{
                for(int i=0; i<nQueens; i++){
                    if(tablero[i]!=objCromo.getTablero()[i]) return false;
                }
            }
        }
        return true;
    }

    public String matrizSolucion(){
	StringBuffer s_buff= new StringBuffer(nQueens*nQueens); 
      for(int i=0; i<nQueens;i++){
	  for(int j=0; j<nQueens;j++){
	    if(j==tablero[i]) s_buff.append("*");
	    else s_buff.append("_");
	    if(j<nQueens-1) s_buff.append("|");
	   
	  }
	s_buff.append("\n");
      }
      return s_buff.toString();
    }
      
}

class ComparadorCromosomas implements Comparator<CromosomaQueens>{

    @Override
    public int compare(CromosomaQueens o1, CromosomaQueens o2) {
        if(o1.getAptitud()<o2.getAptitud()) return 1;
        else if(o1.getAptitud()>o2.getAptitud()) return -1;
        else return 0;
    }
    
}